POI2008 BBB

POI2008 BBB

题目大意：

有一个长度为n的记账单。”+”表示存一元钱，”-“表示取一元钱。现在发现记账单有问题。一开始本来已经有了p元钱，并且知道最后账户上还有q元钱。你需要把账户修改正确，使得：

1. 账户永远不会出现负数。
2. 最后账户上还有q元钱。

你有两种操作：

1. 对某一位取反，耗时x。
2. 把最后一位移到第一位，耗时y。

问最少耗时为多少。

( $n \le 10^6 $ , $0 \le p,q \le 10^6 $ , $ 1 \le x,y \le 1000$ )

题解：

首先有一个想法就是把操作1与操作2分开。先枚举进行操作2的次数，再在此基础上进行操作1以达到要求。

问题就变成了，对于一个固定的字符串，我们只用操作1使得其满足条件。

要满足账户永远不会出现负数，那么只需要满足前缀和最小的那个点的前缀和不小于0即可。

因此我们把前缀和最小的那个点前面的”-“依次变为”+”，则一定可满足这个条件。

接下来还有一个条件，那就是最后账户上还有q元钱。我们只需要加上额外的操作1的次数使其满足即可。(要么把前面的”-“变成”+”，要么把后面的”+”变成”-“)

前缀和最小的那个点，可以用单调队列直接全部预处理出来，复杂度为$O(n)$。

(当然可以用线段树无脑算，复杂度为$O(nlogn)$)

Code:

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
void Rd(int&res){
	res=0;char c;
	while(c=getchar(),c<48);
	do res=res*10+(c&15);
		while(c=getchar(),c>47);
}
const int N=1000001,inf=1<<30;
int n,p,q,x,y,sum[N<<1];
char str[N];
char opt(int i){
	if(i>n)i-=n;
	return str[i];
}
int id[N],que[N<<1];
int main(){
	Rd(n),Rd(p),Rd(q),Rd(x),Rd(y);
	scanf("%s",str+1);
	for(int i=1;i<=n*2;i++){
		if(opt(i)=='+')sum[i]=sum[i-1]+1;
		else sum[i]=sum[i-1]-1;
	}
	int L=1,R=0;
	for(int r=2*n,l=2*n+1;r>n&&l>0;r--){
		while(L<=R&&que[L]>r)L++;
		while(r-l+1<n){
			l--;
			while(L<=R&&sum[que[R]]>=sum[l])R--;
			que[++R]=l;
		}
		id[r-n]=que[L];
	}
	int ans=inf;
	for(int i=1;i<=n;i++){
		int l=i+1,r=i+n,tmp=q-p-sum[n];
		int res=(n-i)*y,dalt=sum[l-1]-sum[id[i]]-p;
		if(dalt>0)res+=(dalt+1)/2*x,tmp-=(dalt+1)/2*2;
		res+=abs(tmp/2)*x;
		ans=min(ans,res);
	}
	printf("%d\n",ans);
	return 0;
}